3、直线
题目 直线
思路分析
每两个点可以确定一条线 但线重合算同一条线
所以可以用哈希去存这些线 可以很好解决重复的问题
问题是如何存下一条线
考虑用 y=kx+b 那么只需要记录k b 即可确定一条线
那么问题就转变成了 枚举每两个点 算他们的kb 存入哈希表中
最后看哈希表的大小即可
另外 斜率不存在的情况 不好处理（斜率公式中 分子为0了）
因为是竖线 所以他和宽度有关 有多少列 就有多少条 拿出来另外处理
#include<bits/stdc++.h>
using namespace std;
typedef pair<double,double> PII;
set<PII> hashtable;
int main()
{
int n,m;
n=20,m=21;
for(int x1=0;x1<n;x1++){
for(int y1=0;y1<m;y1++){
for(int x2=0;x2<n;x2++){
for(int y2=0;y2<m;y2++){
if(x2-x1==0)
continue;
if(x1==x2 && y1==y2)
continue;
double k=(double)(y2-y1)/(x2-x1);
// double b=(double)y1-k*x1;//精度缺失 不能用k做乘法
double b=(double)(x2*y1-x1*y2)/(x2-x1);
hashtable.insert({k,b});
}
}
}
}
cout<<hashtable.size()+n;
return 0;
}
理论存在 但是因为除法会涉及精度
一开始忘了换double 用的int 对于0.5的斜率可能会被存成1
然后人傻了 用unordered_map存 它只会把k当键 而不是k b联合键 正确应该用用PDD 加set
如果用浮点数存 也会因为精度问题表示不准确
所以斜率应该用分数表示 而不是用小数
考虑用｛｛分子，分母｝，b｝的形式当键 用gcd将分子分母化成最简形式 有点麻烦
直接用小数的话 需要用化简后的b公式 不能有缺失精度的k做乘法 int b=y1-k*x1;
把k的公式 带入 通分
得到 \(b=(x2y1-x1y2)/(x2-x1)\)
所以 啧 在想出方法来之后 还有一大堆细节问题
尤其是这个精度问题 映像里已经出现三次了 除法变乘法
得把这个问题整理出来
代码实现
#include<bits/stdc++.h>
using namespace std;
typedef pair<double,double> PII;
set<PII> hashtable;
int main()
{
int n,m;
n=20,m=21;
for(int x1=0;x1<n;x1++){
for(int y1=0;y1<m;y1++){
for(int x2=0;x2<n;x2++){
for(int y2=0;y2<m;y2++){
if(x2-x1==0)
continue;
if(x1==x2 && y1==y2)
continue;
double k=(double)(y2-y1)/(x2-x1);
double b=(double)(x2*y1-x1*y2)/(x2-x1);
hashtable.insert({k,b});
}
}
}
}
cout<<hashtable.size()+n;
return 0;
}
💬 评论